#define _CRT_SECURE_NO_WARNINGS 1
#include <iostream>
#include <map>
#include <vector>
using namespace std;
struct ListNode {
    int val;
    ListNode* next;
    ListNode() : val(0), next(nullptr) {}
    ListNode(int x) : val(x), next(nullptr) {}
    ListNode(int x, ListNode* next) : val(x), next(next) {}
};

ListNode* mergeKLists(vector<ListNode*>& lists) {
    multimap<int, ListNode*> cur;
    for (int n = 0; n < lists.size(); n++)
    {
        while (lists[n])
        {
            cur.insert({ lists[n]->val, lists[n] });
            lists[n] = lists[n]->next;
        }
    }
    ListNode* ret = cur.begin()->second;
    ListNode* retn = ret;
    multimap<int, ListNode*>::iterator it = ++cur.begin();
    while (it != cur.end())
    {
        ret->next = it->second;
        ret = ret->next;
        it++;
    }
    it--;
    it->second->next = nullptr;
    return retn;
}
int main()
{
    vector<ListNode*> cur = {};
    ListNode* lt1 = new ListNode();
    ListNode* lt2 = new ListNode();
    ListNode* lt3 = new ListNode();
    ListNode* lt4 = new ListNode();
    ListNode* lt5 = new ListNode();
    ListNode* lt6 = new ListNode();
    ListNode* lt7 = new ListNode();
    ListNode* lt8 = new ListNode();
    lt1->val = 1;
    lt2->val = 4;
    lt3->val = 5;
    lt4->val = 1;
    lt5->val = 3;
    lt6->val = 4;
    lt7->val = 2;
    lt8->val = 6;
    lt1->next = lt2;
    lt2->next = lt3;
    lt4->next = lt5;
    lt5->next = lt6;
    lt7->next = lt8;
    ListNode* p =  mergeKLists(cur);
    while (p)
    {
        cout << p->val;
        p = p->next;
    }
}
